/*
day395 
2020.9.26 
*/ 

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
		int l=findLeft(nums,target,0,nums.size()-1);
		if(l==-1)
		{
			return 0;
		}
		int r=findRight(nums,target,0,nums.size()-1);
//		cout<<l<<'\t'<<r<<endl; 
		return r-l+1;
    }
    
    int findLeft(vector<int>& nums,int target,int l,int r)
    {
    	if(l>r)
    	{
    		return -1;
		}
		
		int mid=(l+r)/2;
		if(nums[mid]<target)
		{
			return findLeft(nums,target,mid+1,r);
		}
		
		if(nums[mid]>target)
		{
			return findLeft(nums,target,l,mid-1);
		}
		
		if(mid==0 || nums[mid-1]!=target)
		{
			return mid;
		}
		
		return findLeft(nums,target,l,mid-1);
	}
	
	int findRight(vector<int>& nums,int target,int l,int r)
    {
    	if(l>r)
    	{
    		return -1;
		}
		
		int mid=(l+r)/2;
		if(nums[mid]<target)
		{
			return findRight(nums,target,mid+1,r);
		}
		
		if(nums[mid]>target)
		{
			return findRight(nums,target,l,mid-1);
		}
		
		if(mid==nums.size()-1 || nums[mid+1]!=target)
		{
			return mid;
		}
		
		return findRight(nums,target,mid+1,r);
	}
};

int main()
{
	vector<int> nums={5,7,7,8,8,10};
	int target=8;
	Solution s;
	s.search(nums,target);
	return 0;
}
